package com.test.daily.leetcode.y2022.m06.day0604.v01;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/4 下午 11:14
 * @version: 1.0
 */
public class Code03_TopologicalOrderDFS2 {
    public static class DirectedGraphNode{
        int value;
        public ArrayList<DirectedGraphNode> neighbors;
        public DirectedGraphNode(int value, ArrayList<DirectedGraphNode> neighbors){
            this.value = value;
            neighbors = new ArrayList<>();
        }
    }
    public static class Record{
        public DirectedGraphNode node;
        public int nodes;
        public Record(DirectedGraphNode node, int nodes){
            this.nodes = nodes;
            this.node = node;
        }
    }

    public static class MyComparator implements Comparator<Record>{

        @Override
        public int compare(Record o1, Record o2) {
            return o1.nodes - o2.nodes == 0 ? 0: (o1.nodes - o2.nodes > 0)? -1: 1;
        }
    }

    public static ArrayList<DirectedGraphNode> top(ArrayList<DirectedGraphNode> graph){
        HashMap<DirectedGraphNode, Record> order = new HashMap<>();
        for(DirectedGraphNode cur: graph){
            f(cur, order);
        }
        ArrayList<Record> arrRecord = new ArrayList<>();
        for(Record record: order.values()){
            arrRecord.add(record);
        }
        arrRecord.sort(new MyComparator());
        ArrayList<DirectedGraphNode> ans = new ArrayList<>();
        for(Record record: arrRecord){
            ans.add(record.node);
        }
        return ans;
    }
    public static Record f(DirectedGraphNode node, HashMap<DirectedGraphNode, Record> order){
        if(order.containsKey(node)){
            return order.get(node);
        }
        int nodes = 0;
        for(DirectedGraphNode cur: node.neighbors){
            nodes += f(cur, order).nodes;
        }
        Record record = new Record(node, nodes+1);
        order.put(node, record);
        return record;
    }
}
